package leetcode.editor.cn.dsa08_hashtable;
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

public class LongestSubstringWithoutRepeatingCharacters3_4 {
    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters3_4.Solution solution =
                new LongestSubstringWithoutRepeatingCharacters3_4().new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); //3
        System.out.println(solution.lengthOfLongestSubstring("dvdf")); //3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb")); //1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew")); //3
        System.out.println(solution.lengthOfLongestSubstring("")); //0
        System.out.println(solution.lengthOfLongestSubstring("abcdefg")); //7
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最优解：哈希表 + 双指针优化思路
         * 1.哈希表作用变形
         *   字符ASCII码值 --> 字符
         *   字符ASCII码值 --> 字符最后出现索引
         * 2.遇到重复元素后，左指针移动优化
         *   逐个移动到前一个相同字符出现后的位置 -->
         *   一次性定位到前一个相同字符出现后的位置
         *
         * 步骤：
         *   1.初始化哈希表，存入非ASCII码值作为默认值
         *   2.遍历字符串，使用双指针定位子串索引
         *     字符已出现：取出哈希表中记录，左指针到记录+1
         *     无论是否出现，将右指针记录到哈希表
         *   3.每次移动都记录子串长度，保留最大值
         *
         * @param s
         * @return
         */
        public int lengthOfLongestSubstring(String s) {
            int len; // 源字符串长度
            if (s == null || (len = s.length()) == 0) {
                return 0;
            }
            int res = 0, // 最长不重复子串的长度
                left = 0, // 子串最左端字符索引
                right = 0; // 子串最右端字符索引

            // 1.哈希表中填充ASCII码表不包含的数值作为默认值：-1
            int[] arr = new int[128];  // ASCII码 --> 最后一次出现的索引
            for (int i = 0; i < arr.length; i++) {
                arr[i] = -1;
            }
            // 2.遍历字符串的所有字符
            while (right < len) {
                int c = s.charAt(right); // 这里直接转为int，省略了hash函数
                if (arr[c] != -1) { //重复出现
                    // 移动左指针，直接定位到上次出现的下一个索引
                    int start0 = arr[c] + 1;
                    // 因为left移动过的元素没有删除，因此需要判断
                    left = left > start0 ? left : start0; // 只往右不往左
                }
                // 无论是否重复，记录该字符最后一次出现的索引
                arr[c] = right;
                // 3.计算子串长度，记录最大值：右索引+1 - 左索引
                int size = right -left + 1;
                res = res > size ? res : size;
                // 移动右指针
                right++;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}